import java.util.*;

public class 火星词典 {
    //https://leetcode.cn/problems/Jf1JuT/description/
    public String alienOrder(String[] words) {
        //构建图和入度表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            graph.add(new ArrayList<Integer>());
        }
        //没出现的单词用-1表示
        int[] indegree = new int[26];
        Arrays.fill(indegree, -1);
        for (String w : words) {
            for (int i = 0; i < w.length(); i++) {
                indegree[w.charAt(i) - 'a'] = 0;
            }
        }
        //找出拓扑排序构件图
        for (int i = 0; i < words.length - 1; i++) {
            String a = words[i];
            String b = words[i + 1];
            int j = 0;
            for (; j < Math.min(a.length(),b.length()); j++) {
                char x = a.charAt(j);
                char y = b.charAt(j);
                if(x != y){
                    graph.get(x-'a').add(y-'a');
                    indegree[y-'a']++;
                    break;
                }
            }
            //如果比较完成发现前面的都一样比如wrt wr,比较完发现前面还有, 不满足情况直接返回
            if(j < a.length() && j == b.length()){
                return "";
            }
        }
        StringBuilder sb = new StringBuilder();
        //最多只会出现26个字母
        int[] queue = new int[26];
        int l = 0;
        int r = 0;
        int cnt = 0;//记录出现字母数
        for (int i = 0; i < 26; i++) {
            if(indegree[i] != -1){
                cnt++;
            }
            if(indegree[i] == 0){
                queue[r++] = i;
            }
        }
        while(l < r){
            int t = queue[l++];
            sb.append((char)(t + 'a'));
            for(int num : graph.get(t)){
                if(--indegree[num] == 0){
                    queue[r++] = num;
                }
            }
        }
        //出现字母数和顺序不一样就返回""
        return cnt != sb.length() ? "" : sb.toString();
    }
}
